1. Field of the Invention
This invention relates to the field of systems for converting object representations to images for graphical display, and in particular to a system for rendering a surface represented by a set of Bezier patches.
2. Description of the Related Art
There is a growing interest in the graphics, vision, and manufacturing communities to be able to acquire and digitally reproduce the shape and external appearance of objects for the purpose of transmission, display, and numerically controlled fabrication. This would have applications in product design, fast prototyping, reverse engineering, and digitizing shapes for the visual simulation, animation, and entertainment industries. Current advancement in laser range scanners now offers a promising methodology for fully-automated model acquisition of arbitrary objects. Several million points scanned on an arbitrary object can be converted easily into an irregular mesh of polygons. These polygons are then preferably converted into a parametric surface representation, which is a more compact and manipulable form. U.S. Pat. No. 5,999,188 titled "System and method for parametric surface representation of objects using high order surface patches" filed Mar. 3, 1997, and authored by Nishit Kumar et al. provides a fully automated method for converting a polygonal representation into a set of Bezier patches. A method for rendering these patches is now desirable.
A Bezier patch is a two-dimensional Bezier curve. A Bezier curve is defined by the following equation: ##EQU1##
where g.sub.i, 0.ltoreq.i.ltoreq.n, are control points as shown in FIG. 1A. The result is a curve that is formed by a weighted sum of the control points. In cubic form, equation (1) can be represented by the following matrix equation: ##EQU2##
where G.sub.c is a column vector containing the Bezier curve control points. If G.sub.c is parameterized in order to vary as a function of a second coordinate t, this gives the two-dimensional surface: ##EQU3##
Realizing that for 3rd order Bezier curves, G.sub.i (t) can be expressed in the matrix equation EQU G.sub.i (t)=T M G.sub.ci, (4)
an expanded form of equation (3) can be written ##EQU4##
Equation (5) is the matrix form of a bicubic Bezier patch. An example of such a patch is shown in FIG. 1B. Equation (5) is decomposable into three equations of the same form, one equation for each coordinate axis of the control points. For example, equation (5) could be written as EQU X(s,t)=S M G.sub.x M T.sup.T, (6) EQU Y(s,t)=S M G.sub.y M T.sup.T, and (7) EQU Z(s,t)=S M G.sub.z M T.sup.T. (8)
A generalization of the Bezier patch referred to as a "rational Bezier patch" is often used. A rational Bezier patch has a fourth equation
W(s,t)=S M G.sub.w M T.sup.T, (9)
which is used in determining the equation of the points of the surface in the following way: the (x,y,z) points on the surface patch are given by ##EQU5##
where EQU 0.ltoreq.s,t.ltoreq.1. (10)
Three properties of Bezier patches are noted here. A Bezier patch is completely contained within the convex hull formed by the control points which define the patch. One exemplary consequence of this is that it may be determined that a patch is not within the screen boundaries if none of the control points is within the screen boundaries. A desired affine transformation (e.g. rotation, translation, magnification) of a Bezier patch may be achieved by applying the transformation to the control points. An exemplary consequence of this is that the transformation may be applied before the patch is rendered, thereby providing a significant decrease in the associated computation. Finally, an affine transformation may be applied to the s,t parameters of a Bezier patch without inducing any variation in the patch. These three properties will be used in later discussion.
In addition to the surface coordinates of an object, Bezier patches may be used to represent other aspects of the object. Examples include patches which provide values for the normal to the surface (N), the direction of the light source (L), the direction of reflected objects (R), the surface color and opacity of an object (R,G,B,A), and the coordinates of a texture image to be mapped onto the surface (U,V). In addition to these primary attribute patches, secondary attribute patches may also be associated with an object for special effects. All of these attribute patches must be rendered during the rendering of the surface to provide realism and a variety of special effects.
The usage of Bezier patches advantageously provides a method for compact, high-quality representation of objects. This method also allows for efficient execution of affine transformations on the object. It is desirable to have a method for converting Bezier patches into sets of triangles or other polygons for which established graphics rendering hardware exists.